{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "lightgbm是继xgboost之后的又一大杀器，它训练速度快，且精度高，下面就其主要创新点做介绍，本文主要[参考自>>>](https://zhuanlan.zhihu.com/p/99069186)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一.单边梯度采样算法\n",
    "GOSS(Gradient-based One-Side Sampling)是一种样本采样方法，它基于梯度的绝对值对样本进行采样，主要包含如下几个步骤：   \n",
    "\n",
    "（1）对梯度的绝对值进行降序排序，选择前$a*100\\%$个样本；   \n",
    "\n",
    "（2）从剩下的小梯度数据中随机选择$b*100\\%$个样本，为了不破坏原始数据的分布特性，对这$b*100\\%$个样本权重扩大$\\frac{1-a}{b}$倍（代价敏感学习）   \n",
    "\n",
    "（3）将这$(a+b)*100\\%$个样本用作为下一颗树的训练\n",
    "\n",
    "算法流程如下：   \n",
    "\n",
    "![avatar](./source/10_goss.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二.互斥特征捆绑算法\n",
    "EFB(Exclusive Feature Bundling)可以粗略的理解为one-hot的逆过程，我们可以将这个过程拆解为两步：   \n",
    "\n",
    "（1）第一步，需要寻找那些特征进行捆绑，理想情况下所选择的几个特征，每行只有一个非0值，但现实数据可能没有那么离线，lgb用了一种允许一定误差的图着色算法求解：  \n",
    "\n",
    "![avatar](./source/10_特征捆绑.png)   \n",
    "\n",
    "（2）第二步，便是合并这些特征，如果直接合并其实是有问题的，比如下面第一张图片，因为第一列特征的取值1和第二列特征的取值1其实具有不同含义，所以lgb的做法是对每一列加上一个bias，这个bias为前面所有特征列的max取值之和，如下面第二张图例所示：  \n",
    "\n",
    "![avatar](./source/10_efb.png)  \n",
    "\n",
    "算法流程如下，但有一点需要注意是，计算特征的切分点是在各自的range内计算的，如上图，虽然合并后为一列特征，但需要分别在[1,2],[3,4],[5,8]这三个区间内分别计算一个切分点 \n",
    "\n",
    "![avatar](./source/10_捆绑特征合并.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 三.类别特征优化\n",
    "\n",
    "类别特征，特别是高基类别特征的处理一直很棘手，比如日期，id等特征，如果按照常规方法对其作one-hot展开，在训练决策树时会切分出很多不平衡的结点来（比如左节点样本数远大于右节点），这本质是一种one-vs-rest的切分方法，收益很低，决策树还容易过拟合，而lgb提出了使用many-vs-many的方法对类别特征进行划分，这样既能平衡左右节点的训练样本量，又能一定程度上避免过拟合，示例如下（图中决策判断条件如果为True则走左分支，否则走右边）：   \n",
    "\n",
    "![avatar](./source/10_lgb中类别特征的处理.png)   \n",
    "\n",
    "当然，如果暴力搜索时间复杂度会有些高，假如某类别特征有$k$种取值的可能，那么共有如下的$2^{k-1}-1$种搜索结果，时间复杂度为$O(2^k)$：  \n",
    "\n",
    "$$\n",
    "C_k^1+C_k^2+\\cdots+C_k^{k//2}=2^{k-1}-1\n",
    "$$   \n",
    "\n",
    "lgb基于《On Grouping For Maximum Homogeneity》实现了时间复杂度为$O(klogk)$的求法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
